package com.yun.algorithmproblem.leetcode;

public class Leetcode3297 {

    public static void main(String[] args) {
        Leetcode3297 obj=new Leetcode3297();
        String word1="abcabc";
        String word2="aaabc";
        System.out.println(obj.validSubstringCount(word1, word2));
    }

    public long validSubstringCount(String word1, String word2) {
        int length1 = word1.length();
        int length2 = word2.length();
        if(length1 < length2){
            return 0;
        }
        long ans=0;
        int[] word1Array=new int[26];
        char[] word1CharArray = word1.toCharArray();
        for (int i = 0; i < length2; i++) {
            word1Array[word1CharArray[i]-97]++;
        }
        int[] word2Array=new int[26];
        char[] word2CharArray = word2.toCharArray();
        for (char c : word2CharArray) {
            word2Array[c-97]++;
        }
        int left=0,right= length2 -1;
        while (right< length1){
            if(arrayContain(word1Array,word2Array)){
                ans+= length1 -right;
                word1Array[word1CharArray[left]-97]--;
                left++;
            }else {
                right++;
                if(right< length1){
                    word1Array[word1CharArray[right]-97]++;
                }
            }
        }
        return ans;
    }

    private boolean arrayContain(int[] array1,int[] array2){
        for (int i = 0; i < array1.length; i++) {
            if(array1[i]<array2[i]){
                return false;
            }
        }
        return true;
    }
}
